| 翻訳と辞書 |
| Dominance drawing ： ウィキペディア英語版 |
Dominance drawing
Dominance drawing is a style of graph drawing of directed acyclic graphs that makes the reachability relations between vertices visually apparent. In dominance drawing, vertices are placed at distinct points of the Euclidean plane and a vertex ''v'' is reachable from another vertex ''u'' if and only if both Cartesian coordinates of ''v'' are greater than or equal to the coordinates of ''u''. The edges of a dominance drawing may be drawn either as straight line segments, or, in some cases, as polygonal chains.〔
==Planar graphs==
Every transitively reduced ''st''-planar graph, a directed acyclic planar graph with a single source and a single sink, both on the outer face of some embedding of the graph, has a dominance drawing. The left-right algorithm for finding these drawings sets the ''x'' coordinate of every vertex to be its position in a depth-first search ordering of the graph, starting with ''s'' and prioritizing edges in right-to-left order, and by setting the ''y'' coordinate to be obtained in the same way but prioritizing edges in left-to-right order. Typical dominance drawing algorithms include another phase of compaction after this coordinate assignment, shifting vertices down and to the left as much as possible while preserving the properties of a dominance drawing. The resulting drawing lies within an ''n'' × ''n'' integer grid, and displays many of the symmetries of the underlying topological embedding. This drawing, and more generally every dominance drawing of a transitively-reduced ''st''-planar graph, is necessarily planar, with straight-line edges.〔〔
For ''st''-planar graphs that are not transitively reduced, an equivalent transitively reduced graph may be obtained by subdividing each edge. However, a straight-line drawing of the resulting transitively reduced graph will form a drawing of the original graph in which some edges have bends, at the dummy vertices introduced by the subdivision.〔〔 A planar dominance drawing is not necessarily an upward planar drawing, because some edges may be horizontal, but rotating it by 45° necessarily gives an upward planar drawing.〔 In a comparison with other methods for drawing directed acyclic graphs, the left-right algorithm (together with a planarization preprocessing step) was found to perform well in terms of the area of the drawings it produces, the number of bends, and the aspect ratio of the drawing, but less well in total edge length.〔
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Dominance drawing」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|